#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;

int start, end;
int prime[10000 + 10];
int visited[10000 + 10];
int step[10000 + 10];

bool prime_determine(int n) {
  if (!(n & 1)) {
    return false;
  } else {
    int i, s;
    s = (int) sqrt(n);
    for (i = 3; i <= s; i += 2) {
      if (n % i == 0) {
        return false;
      }
    }
  }
  return true;
}

int change(int n, int p, int d) {
  if (p == 4) {
    return d * 1000 + n % 1000;
  }
  else if (p == 3) {
    return (n / 1000) * 1000 + d * 100 + n % 100;
  }
  else if (p == 2) {
    return (n / 100) * 100 + d * 10 + n % 10;
  }
  else {
    return (n / 10) * 10 + d;
  }
}

int main() {
  memset(prime, 0, sizeof(prime));
  for (int i = 1000; i < 10000; i++) {
    if (prime_determine(i)) {
      prime[i] = 1;
    }
  }
  
  int c;  
  scanf("%d", &c);
  for (int i = 0; i < c; i++) {
    scanf("%d %d", &start, &end);
    
    memset(visited, 0, sizeof(visited));
    memset(step, 0, sizeof(step));
    queue<int> que;
    que.push(start);
    while (!que.empty()) {
      int n, cur_step, tmpn;
      n = que.front();
      que.pop();
      cur_step = step[n];
      if (n == end) {
        printf("%d\n", step[n]);
        break;
      }
      
      for (int p = 4; p > 0; p--) {
        for (int d = 0; d < 10; d++) {
          if (p == 4 && d == 0) {
            continue;
          }
          
          tmpn = change(n, p, d);
          if (prime[tmpn] == 1 && visited[tmpn] == 0) {
            que.push(tmpn);
            visited[tmpn] = 1;
            step[tmpn] = cur_step + 1;
          }
        }
      }
    }
  }
  
  return 0;
}
